package leetcode.动态规划和贪心;

import java.util.Arrays;

/**
 * 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
 *
 * 示例 1:
 *
 * 输入: 2
 * 输出: 1
 * 解释: 2 = 1 + 1, 1 × 1 = 1。
 */
public class Test343整数拆分 {

    static int[] record;

    public static int integerBreak(int n) {
        record = new int[n + 1];
        Arrays.fill(record, -1);
        return dp(n);
    }


    public static int dp(int n) {
        // 1 是不可再分的，返回 1 * 上一个数
        if (n == 1)
            return 1;
        // n 被计算过了就不要再计算了
        if (record[n] != -1)
            return record[n];
        int res = -1;
        // 遍历、分解每个 i
        // 一定要将单个 n 分为两部分来处理
        for (int i = 1; i <= n - 1; i++) {
            res = max3(res, i * (n - i), i * dp(n - i));
        }
        // 记录本次找的值
        record[n] = res;
        return res;
    }

    public static int max3(int res, int i, int i1) {
        return Math.max(res, Math.max(i, i1));
    }

    public static void main(String[] args) {
        System.out.println(integerBreak2(2));
    }


    /**
     * dp 解法
     * 转移方程：
     * dp[i] = max(2 * dp[i - 2], 3 * dp[i - 3])
     * <p>
     * <p>
     * 因为当 n > 4 时，n 在拆分后，最优解只包含 3 和 2，其中 2 的个数可能为 0，
     * 利用i = 2 + (i - 2) 或者 i = 3 + (i - 3)，即 i 如果拆分出一个 2 了，
     * 则剩下的数可以根据 dp[i-2] 来直接求出， i 如果拆分出一个 3 了，
     * 则剩下的数可以根据 dp[i-3] 来直接求出，再比较两者中的最大值即可。
     */
    public static int integerBreak2(int n) {
        if (n <= 3)
            return n - 1;
        int[] dp = new int[n + 1];
        // dp[i] 代表 n = i 时，拆分后可获得的最大乘积
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for (int i = 4; i <= n; ++i) { // i++ 和 ++i 是一样的，区别是，++i 会提前判断出终止的时机，加快算法运行速度
            // i - 2 一定计算过了，i - 2 + 2 = i
            // 我们将越来越大的数，都归还到最开始的几个问题上
            // 例如现在是 4, 4 - 2 = 2，和 2 再相乘得最大值
            // 假设是 44 呢？ 44 - 2 = 22, 这个 22 之前一定算过了的，因为 22 - 2 = 20,
            // 20 - 2 = 18。。。随着数据月来越大，它之前的数据一定会被计算过并存储在 dp 里面
            dp[i] = Math.max(2 * dp[i - 2], 3 * dp[i - 3]);
        }
        return dp[n];
    }
}
